翻訳と辞書 Words near each other ・ Hope chest (disambiguation) ・ Hope Christian College ・ Hope Christian School ・ Hope Christian School (Masaka, Uganda) ・ Hope Church ・ Hope City ・ Hope City Church ・ Hopantenic acid ・ Hopar Valley ・ Hopatcong High School ・ Hopatcong Public Schools ・ Hopatcong State Park ・ Hopatcong, New Jersey ・ HopC RNA motif ・ Hopcalite ・ Hopcroft–Karp algorithm ・ Hope ・ Hope & Anchor Front Row Festival ・ Hope & Co. ・ Hope & Faith ・ Hope & Faith (season 1) ・ Hope & Glory (album) ・ Hope & Glory (song) ・ Hope & Heroes Children's Cancer Fund ・ Hope & Other Sins ・ Hope & Ruin ・ Hope & Ruin (song) ・ Hope & Sorrow ・ Hope (1817 ship) ・ Hope (2006 film) Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Hopcroft–Karp algorithm ： ウィキペディア英語版 Hopcroft–Karp algorithm In computer science, the Hopcroft–Karp algorithm is an algorithm that takes as input a bipartite graph and produces as output a maximum cardinality matching – a set of as many edges as possible with the property that no two edges share an endpoint. It runs in $O(|E|\backslash sqrt)$ time in the worst case, where $E$ is set of edges in the graph, and $V$ is set of vertices of the graph. In the case of dense graphs the time bound becomes $O(|V|^)$, and for random graphs it runs in near-linear time. The algorithm was found by . As in previous methods for matching such as the Hungarian algorithm and the work of , the Hopcroft–Karp algorithm repeatedly increases the size of a partial matching by finding augmenting paths. However, instead of finding just a single augmenting path per iteration, the algorithm finds a maximal set of shortest augmenting paths. As a result, only $O(\backslash sqrt)$ iterations are needed. The same principle has also been used to develop more complicated algorithms for non-bipartite matching with the same asymptotic running time as the Hopcroft–Karp algorithm. ==Augmenting paths== A vertex that is not the endpoint of an edge in some partial matching $M$ is called a ''free vertex''. The basic concept that the algorithm relies on is that of an ''augmenting path'', a path that starts at a free vertex, ends at a free vertex, and alternates between unmatched and matched edges within the path. Augmented path can have only two vertices (both free) and single unmatched edge between them. Note that except for the endpoints, all other vertices (if any) in augmented path must be non-free vertices. If $M$ is a matching, and $P$ is an augmenting path relative to $M$, then the symmetric difference of the two sets of edges, $M\; \backslash oplus\; P$, would form a matching with size $|M|\; +\; 1$. Thus, by finding augmenting paths, an algorithm may increase the size of the matching. Conversely, suppose that a matching $M$ is not optimal, and let $P$ be the symmetric difference $M\; \backslash oplus\; M^$ * where $M^$ * is an optimal matching. Then $P$ must form a collection of disjoint augmenting paths and cycles or paths in which matched and unmatched edges are of equal number; the difference in size between $M$ and $M^$ * is the number of augmenting paths in $P$. Thus, if no augmenting path can be found, an algorithm may safely terminate, since in this case $M$ must be optimal. An augmenting path in a matching problem is closely related to the augmenting paths arising in maximum flow problems, paths along which one may increase the amount of flow between the terminals of the flow. It is possible to transform the bipartite matching problem into a maximum flow instance, such that the alternating paths of the matching problem become augmenting paths of the flow problem.〔, section 12.3, bipartite cardinality matching problem, pp. 469–470.〕 In fact, a generalization of the technique used in Hopcroft–Karp algorithm to arbitrary flow networks is known as Dinic's algorithm. : Input: Bipartite graph $G(U\; \backslash cup\; V,\; E)$ : Output: Matching $M\; \backslash subseteq\; E$ : $M\; \backslash leftarrow\; \backslash empty$ : repeat :: $\backslash mathcal\; P\; \backslash leftarrow\; \backslash$ ''maximal set of vertex-disjoint shortest augmenting paths'' :: $M\; \backslash leftarrow\; M\; \backslash oplus\; (P\_1\; \backslash cup\; P\_2\; \backslash cup\; \backslash dots\; \backslash cup\; P\_k)$ : until $\backslash mathcal\; P\; =\; \backslash empty$ 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Hopcroft–Karp algorithm」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.